package leetcode.lcp;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution1 implements IDebug {
//	int[] materials;
	int[][] cookbooks;
	int[][] attribute;
	int limit;
	int len;

	public int perfectMenu(int[] materials, int[][] cookbooks, int[][] attribute, int limit) {
//		this.materials = materials;
		this.cookbooks = cookbooks;
		this.attribute = attribute;
		this.limit = limit;
		this.len = cookbooks.length;
		int size = 1 << len;
		Integer[] dp = new Integer[size];
		return cook(materials, 0, 0, 0, dp, 0);
	}

	private int cook(int[] materials, int index, int happy, int full, Integer[] dp, int path) {
		if (index == this.len) {
			int ans = full >= limit ? happy : -1;
			dp[path] = ans;
			return ans;
		}
		if (dp[path] != null) {
			return dp[path];
		}
		int[] book = this.cookbooks[index];
		boolean enough = true;
		for (int i = 0; i < 5; i++) {
			if (materials[i] < book[i]) {
				enough = false;
				break;
			}
		}
		int max = this.cook(materials, index + 1, happy, full, dp, path);
		if (enough) {
			int[] nexts = new int[5];
			for (int i = 0; i < 5; i++) {
				nexts[i] = materials[i] - book[i];
			}
			max = Math.max(max, this.cook(nexts, index + 1, happy + attribute[index][0], full + attribute[index][1], dp,
					(path | (1 << index))));
		}
		dp[path] = max;
		return max;
	}

	@Override
	public void debug4() {
		H.compare(7, this.perfectMenu(H.str2array3("[3,2,4,1,2]"),
				H.str2array1("[[1,1,0,1,2],[2,1,4,0,0],[3,2,4,1,0]]"), H.str2array1("[[3,2],[2,4],[7,6]]"), 5));
		H.compare(11, this.perfectMenu(H.str2array3("[10,10,10,10,10]"),
				H.str2array1("[[1,1,1,1,1],[3,3,3,3,3],[10,10,10,10,10]]"), H.str2array1("[[5,5],[6,6],[10,10]]"), 1));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
